<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
      <title>GTL - Graph Template Library: topsort.h Source File</title>
      <link href="doxygen.css" rel="stylesheet" type="text/css">
  </head>
  <body>
    <p class="links">  
      <a href="../index.html">Home</a> |
      Documentation |
      <a href="../register.html">Download</a> |
      <a href="../platforms.html">Platforms</a> |
      <a href="../refer.html">Projects</a> |      
      <a href="../lists.html">Mailing Lists</a> |
      <a href="../history.html">Version History</a>
    </p>

<!-- Generated by Doxygen 1.5.3 -->
<div class="tabs">
  <ul>
    <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
    <li><a href="classes.html"><span>Classes</span></a></li>
    <li class="current"><a href="files.html"><span>Files</span></a></li>
    <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
  </ul>
</div>
<h1>topsort.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">//==========================================================================</span>
<a name="l00002"></a>00002 <span class="comment">//</span>
<a name="l00003"></a>00003 <span class="comment">//   topsort.h </span>
<a name="l00004"></a>00004 <span class="comment">//</span>
<a name="l00005"></a>00005 <span class="comment">//==========================================================================</span>
<a name="l00006"></a>00006 <span class="comment">// $Id: topsort.h,v 1.8 2000/09/11 07:36:43 raitner Exp $</span>
<a name="l00007"></a>00007 
<a name="l00008"></a>00008 <span class="preprocessor">#ifndef GTL_TOPSORT</span>
<a name="l00009"></a>00009 <span class="preprocessor"></span><span class="preprocessor">#define GTL_TOPSORT</span>
<a name="l00010"></a>00010 <span class="preprocessor"></span>
<a name="l00011"></a>00011 <span class="preprocessor">#include &lt;GTL/GTL.h&gt;</span>
<a name="l00012"></a>00012 <span class="preprocessor">#include &lt;GTL/dfs.h&gt;</span>
<a name="l00013"></a>00013 
<a name="l00014"></a>00014 __GTL_BEGIN_NAMESPACE
<a name="l00015"></a>00015 
<a name="l00034"></a><a class="code" href="a00028.html">00034</a> <span class="keyword">class </span>GTL_EXTERN <a class="code" href="a00028.html" title="Topological sorting.">topsort</a> : <span class="keyword">public</span> <a class="code" href="a00008.html" title="Depth-First-Search (DFS) algorithm.">dfs</a> 
<a name="l00035"></a>00035 {
<a name="l00036"></a>00036 <span class="keyword">public</span>:
<a name="l00042"></a><a class="code" href="a00028.html#76a9055969b9dbf006320040be9fd5e6">00042</a>     <a class="code" href="a00028.html" title="Topological sorting.">topsort</a> () : <a class="code" href="a00008.html" title="Depth-First-Search (DFS) algorithm.">dfs</a> () {whole_graph = <span class="keyword">true</span>; acyclic = <span class="keyword">true</span>;}
<a name="l00043"></a>00043 
<a name="l00050"></a><a class="code" href="a00028.html#71069dab2159b75a324f3b8a44a88ced">00050</a>     <span class="keywordtype">int</span> top_num (<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n)<span class="keyword"> const </span>
<a name="l00051"></a>00051 <span class="keyword">        </span>{ <span class="keywordflow">return</span> top_numbers[n]; }
<a name="l00052"></a>00052 
<a name="l00058"></a><a class="code" href="a00028.html#6df72e7e38299c30695e9391c3b04383">00058</a>     <span class="keywordtype">bool</span> is_acyclic ()<span class="keyword"> const</span>
<a name="l00059"></a>00059 <span class="keyword">        </span>{ <span class="keywordflow">return</span> acyclic; }
<a name="l00060"></a>00060 
<a name="l00064"></a>00064     <span class="keyword">typedef</span> list&lt;node&gt;::const_iterator topsort_iterator;
<a name="l00065"></a>00065 
<a name="l00071"></a><a class="code" href="a00028.html#f2b446d051fceb0df31df7057e03025b">00071</a>     topsort_iterator top_order_begin()<span class="keyword"> const</span>
<a name="l00072"></a>00072 <span class="keyword">        </span>{ <span class="keywordflow">return</span> top_order.begin(); }
<a name="l00073"></a>00073 
<a name="l00079"></a><a class="code" href="a00028.html#b4d0debf92c9e5eeceec48856af4b329">00079</a>     topsort_iterator top_order_end()<span class="keyword"> const</span>
<a name="l00080"></a>00080 <span class="keyword">        </span>{ <span class="keywordflow">return</span> top_order.end(); }
<a name="l00081"></a>00081 
<a name="l00094"></a>00094     <span class="keyword">virtual</span> <span class="keywordtype">int</span> <a class="code" href="a00008.html#908f4ea617ed59767ed334b39a2771d0" title="Checks whether the preconditions for DFS are satisfied.">check</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00095"></a>00095 
<a name="l00100"></a>00100     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#1c893f699517cc72624cf171b7bc4da4" title="Resets algorithm.">reset</a> ();
<a name="l00101"></a>00101 
<a name="l00105"></a>00105     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#cc82574cd42ab8256e685374bee5fabb" title="Handler called before the start of DFS.">init_handler</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00106"></a>00106 
<a name="l00110"></a>00110     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#8071fc4e82deff7ceb2790cd4eb42280" title="Handler called after all the adjacent edges of n have been examined.">leave_handler</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp;, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp;, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp;);
<a name="l00111"></a>00111 
<a name="l00115"></a>00115     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00008.html#df1c667188e632761c63f529537c544c" title="Handler called when a already marked node n connected to the actual node by e is...">old_adj_node_handler</a> (<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp;, <a class="code" href="a00010.html" title="An edge in a graph.">edge</a>&amp;, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp;);
<a name="l00116"></a>00116 
<a name="l00117"></a>00117 <span class="keyword">protected</span>:
<a name="l00121"></a>00121     <span class="keywordtype">int</span> act_top_num;
<a name="l00125"></a>00125     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a> top_numbers;
<a name="l00129"></a>00129     list&lt;node&gt; top_order;
<a name="l00133"></a>00133     <span class="keywordtype">bool</span> acyclic;
<a name="l00134"></a>00134 };
<a name="l00135"></a>00135 
<a name="l00136"></a>00136 __GTL_END_NAMESPACE
<a name="l00137"></a>00137 
<a name="l00138"></a>00138 <span class="preprocessor">#endif // GTL_TOPSORT</span>
<a name="l00139"></a>00139 <span class="preprocessor"></span>
<a name="l00140"></a>00140 <span class="comment">//--------------------------------------------------------------------------</span>
<a name="l00141"></a>00141 <span class="comment">//   end of file</span>
<a name="l00142"></a>00142 <span class="comment">//--------------------------------------------------------------------------</span>
</pre></div>    <p class="links">
      <a href="http://www.uni-passau.de/">University of Passau</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/">FMI</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/fmi/lehrstuehle/brandenburg/">Theoretical
	Computer Science</a>
    </p>
  <div class="copyright">
      Design &copy; 2002, 2003 <a href="mailto:raitner@fmi.uni-passau.de">Marcus Raitner</a>,  University of Passau 
  </div>
</body>
</html>
